//
//  53. 最大字序和(贪心解法).swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/20.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution53_2 {
    // 最大和的连续子数组
    // 从贪心的角度：是连续的子数组，最大和的连续子数组，找到和为正数的一段。
    func maxSubArray(_ nums: [Int]) -> Int {
        var result: Int = Int.min
        var curResult: Int = 0
        for i in 0..<nums.count {
            curResult = curResult + nums[i]
            result = max(curResult, result)
            if curResult <= 0 {
                curResult = 0
            }
        }
        return result
    }
    
    
    // 最大子序和
    // 采用贪心
    func maxSubArray2(_ nums: [Int]) -> Int {
        var result = 0
        var sum = 0
        for item in nums {
            sum += item
            result = max(sum, result)
            if sum <= 0 {
                sum = 0
            }
        }
        return result
    }
    static func test() {
                let nums = [-2,1,-3,4,-1,2,1,-5,4]
//        let nums = [-1]
        let result = Solution53_2().maxSubArray2(nums)
        print(result)
    }
}
